Низхідний синтаксичний аналіз
Загальна характеристика і проблеми низхідного аналізу
При низхідному синтаксичному аналізі вивід для заданого вхідного ланцюжка будують, виходячи з початкового символу граматики (аксіоми), тобто побудова дерева синтаксичного розбору починається з кореня і розгортається до листя. Для цього аналізуються декілька перших символів вхідного ланцюжка, і приймається рішення, яке саме правило для аксіоми варто застосувати, а після цього робиться спроба розпізнати елементи правої частини цього правила, визначаючи їх як проміжні цілі (підцілі).
Нехай вхідний рядок має вигляд EMBED Equation.3 . Припустимо, що даний рядок належить вхідній мові, тому повинен існувати вивід
EMBED Equation.3 .
Нехай для аксіоми вибрано правило EMBED Equation.3 , отже, робиться припущення, що
EMBED Equation.3 .
Якщо серед символів EMBED Equation.3 є термінальні символи, то такі самі термінальні символи повинні повинні бути і у рядку EMBED Equation.3 , розбиваючи вхідний рядок на частини. Кожен з нетермінальних символів EMBED Equation.3 визначає підціль.
EMBED Equation.3
(ланцюжок EMBED Equation.3 знаходиться між розпізнаними термінальними символами).
Пошук підцілі приводить до пошуку допоміжних підцілей і т.д. до того часу, поки не приводить до порівняння символів аналізованого ланцюжка з деякими термінальними символами, після чого робиться висновок, чи досягнута загальна мета (чи належить ланцюжок породжуваній мові). Коли розпізнані всі підцілі, тоді розпізнана і загальна ціль. Якщо деяку підціль розпізнати не вдається, потрібно повернутись на крок назад і сформувати нову підціль (якщо було декілька можливих варіантів формування підцілі). Процес завершується або тоді, коли знайдено потрібний вивід, або встановлено, що такого виводу не існує (мета недосяжна).
Характерна риса методів низхідного розбору полягає у тому, що стан алгоритму (поточна підціль) використовується як допоміжна інформація при прийнятті рішення. Розпізнавання підцілей виконується зліва направо.
Приклад. Нехай задано граматику
EMBED Equation.3
Побудувати дерево виводу для ланцюжка EMBED Equation.3 . Виходячи з припущення, що рядок належить породжуваній мові, доходимо висновку про існування виводу EMBED Equation.3 або виводу EMBED Equation.3 (два можливих варіанти). Якщо припустити, що EMBED Equation.3 , то формуються дві підцілі EMBED Equation.3 і EMBED Equation.3 , які розпізнаються незалежно одна від одної.
Так, з EMBED Equation.3 випливає, що EMBED Equation.3 або EMBED Equation.3 . Очевидно, що твердження EMBED Equation.3 є неправильним. Залишається EMBED Equation.3 , тобто EMBED Equation.3 . Таким чином, підціль EMBED Equation.3 розпізнано. Аналогічно розпізнаємо підціль EMBED Equation.3 .
У загальному випадку, у процесі низхідного аналізу, виникають такі проблеми.
1. Ціль (підціль) визначається, використовуючи правило з лівою рекурсією.
Якщо EMBED Equation.3 − ціль, і перше правило для EMBED Equation.3 має вигляд EMBED Equation.3 , то у відповідності з даним методом буде сформовано підціль EMBED Equation.3 . У свою чергу, допоміжною підціллю знову буде EMBED Equation.3 і т.д.
Таким чином, для застосування методу низхідного аналізу, потрібно буде перетворити граматику, щоб усунути ліву рекурсію.
2. Якщо для нетермінальних символів є декілька альтернативних правил виводу
EMBED Equation.3
Як вгадати, яким з ланцюжків EMBED Equation.3 потрібно замінити нетермінальний символ EMBED Equation.3 ? Загального методу немає. Є деякі рекомендації.
Впорядкувати правила так, щоб найбільш ймовірні альтернативи вибирались першими. Зазвичай першою вибирають найдовшу альтернативу. Але у тому випадку, коли вхідний рядок містить помилку, все одно доведеться перебрати всі альтернативи.
Заглядати вперед на 1-2 символи, що дозволяє точн...
